DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2021.26

SOS Lower Bound for Exact Planted Clique

Authors: Shuo Pang

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract

We prove a SOS degree lower bound for the planted clique problem on the Erdös-Rényi random graph G(n,1/2). The bound we get is degree d = Ω(ε²log n/log log n) for clique size ω = n^{1/2-ε}, which is almost tight. This improves the result of [Barak et al., 2019] for the "soft" version of the problem, where the family of the equality-axioms generated by x₁+...+x_n = ω is relaxed to one inequality x₁+...+x_n ≥ ω. As a technical by-product, we also "naturalize" certain techniques that were developed and used for the relaxed problem. This includes a new way to define the pseudo-expectation, and a more robust method to solve out the coarse diagonalization of the moment matrix.

Cite as

Shuo Pang. SOS Lower Bound for Exact Planted Clique. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 26:1-26:63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{pang:LIPIcs.CCC.2021.26,
  author =	{Pang, Shuo},
  title =	{{SOS Lower Bound for Exact Planted Clique}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{26:1--26:63},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.26},
  URN =		{urn:nbn:de:0030-drops-143000},
  doi =		{10.4230/LIPIcs.CCC.2021.26},
  annote =	{Keywords: Sum-of-Squares, planted clique, random graphs, average-case lower bound}
}

Search Results

Documents authored by Pang, Shuo

SOS Lower Bound for Exact Planted Clique

Abstract

Cite as

Thanks for your feedback!

Could not send message